package com.kehao.leetcode.hard.linkedlist;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class SortListSolution {
    private class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode sortList(ListNode head) {
        ListNode fakeHead = new ListNode();
        if(head==null||head.next ==null) return head;
        if(head.next.next == null) {
            if(head.val>head.next.val){
                int tmp = head.val;
                head.val = head.next.val;
                head.next.val = tmp;
            }
            return head;
        }
        else {
            ListNode slow,fast;
            slow  = head;
            fast = head.next.next;
            for (int i = 0;fast!=null; i++) {
                if(i % 2 == 0) slow=slow.next;
                fast= fast.next;
            }
            ListNode mid = slow.next;
            slow.next = null;
            head = sortList(head);
            mid = sortList(mid);
            ListNode p1=head,p2=mid;
            ListNode p = fakeHead;
            while (p1!=null&&p2!=null){
                if(p1.val<p2.val){
                    p.next = p1;
                    p=p.next;
                    p1=p1.next;
                }else {
                    p.next = p2;
                    p2 = p2.next;
                    p=p.next;
                }
            }
            if(p1!=null){
                p.next = p1;
            }
            if(p2!=null){
                p.next = p2;
            }

        }
        return fakeHead.next;
    }
    
    private ListNode getListNodeByArray(int[] intArray){
        ListNode head = new ListNode();
        ListNode tmp = head;
        for (int i = 0; i < intArray.length; i++) {
            ListNode node = new ListNode(intArray[i]);
            tmp.next = node;
            tmp = node;
        }
        return head.next;
    }

    private void printListNode(ListNode node){
        while (node!=null){
            System.out.print(node.val+" ");
            node = node.next;
        }
        System.out.println();
    }

    private List<Integer> listNodeToList(ListNode node){
        List<Integer> list = new ArrayList();
        while (node!=null) {
            list.add(node.val);
            node = node.next;
        }
        return list;
    }
    
    @Test
    public void test01(){
        int[] intArray = {4,2,1,3};
        ListNode head = getListNodeByArray(intArray);
        printListNode(head);
        head = sortList(head);
        printListNode(head);
    }

    @Test
    public void test02(){
        int[] intArray = {4,19,14,5,-3,1,8,5,11,15};
        ListNode head = getListNodeByArray(intArray);
        printListNode(head);
        head = sortList(head);
        printListNode(head);
    }


}
